1. Field of the Invention
The present invention relates to a packet transfer apparatus, and particularly to a packet transfer apparatus which constitutes a network and has a packet retrieval system for power saving.
2. Background Art
By the spread of a broadband service such as Asymmetric Digital Subscriber (ADSL) or Fiber To The Home (FTTH), streaming use of motion picture and sound promoted on the background of these broadband services, the raise of Peer to Peer (P2P) application and the like, Internet traffic increases exponentially, and it appears that this tendency continues after this (see, for example, non-patent document 1).
In order to configure a network which can cope with the increase of the Internet traffic, a packet transfer apparatus such as a high speed and large capacity router or a switch is required. Then, a process which becomes a bottle neck to the speed-up of the packet transfer apparatus and an example of a method of solving it will be described below.
A packet transfer apparatus performs a route retrieval for determining an output line of a received packet based on a destination IP address included in header information of the received packet or a destination MAC address, filtering for determining transfer advisability of a packet based on more detailed header information, or a flow retrieval for determining Quality of Service (QoS) as transfer priority of a packet.
In the case of the route retrieval, for each received packet, reference is made to a route table including, for example, hundreds of thousands of entries in which packet output lines are registered for the respective destination IP addresses or the respective destination MAC addresses, and the output line corresponding to the destination IP address of the received packet or the destination MAC address is determined.
In the case of the flow retrieval, a flow as the kind of a packet is defined as a combination of various header information such as a source IP address, a source MAC address, a Type of Service (TOS) in which priority is defined, a transmission source port to identify a communication use, a destination port and the like in addition to the destination IP address and the destination MAC address. For each of received packets, reference is made to a flow retrieval table including flow entries in which the flow definition is registered, the flow to which the received packet fits is identified, and transfer advisability based on previously set filtering or QoS is determined for each flow.
Since these retrieval processes require retrieval of a large capacity table or table retrieval based on many retrieval conditions, these are particularly heavy-load processes among processes in the packet transfer apparatus, and they are one of bottle necks to the speed-up of the packet transfer apparatus. Then, in a recent high-speed large-capacity packet transfer apparatus, a Content Addressable Memory (CAM) which is a high-speed device dedicated to retrieval is used for the route retrieval or the flow retrieval.
FIG. 19 shows a flow of a retrieval process by a CAM. A CAM 400 includes plural retrieval entries 1900 to 1909 having the same bit length. The bit length and the entry number of the retrieval entries of the CAM 400 are set according to the structure corresponding to the use of the CAM 400. For example, when the CAM 400 is applied to a route table, setting is made so that the structure satisfies the bit length and the entry number of route entries, and when the CAM 400 is applied to a flow retrieval table, setting is made so that the structure satisfies the bit length and the entry number of the flow entries.
A bit denoted by “x” of the retrieval entry is called a mask bit, and is a bit which is determined to be consistent even when the bit of a retrieval key 1910 is 0 or 1. When the retrieval key 1910 having the same bit length as the retrieval entry is inputted to the CAM 400, based on the retrieval key 1910, all the retrieval entries 1900 to 1909 of the CAM 400 are simultaneously compared for consistency, and when there is a consistent retrieval entry, hit information indicating the consistency and a hit address 1911 are outputted. The retrieval entries 1900 to 1909 are not sequentially compared for consistency, but all the retrieval entries 1900 to 1909 are simultaneously compared for consistency, and therefore, there is a feature that the retrieval can be performed at high speed. Incidentally, when there are plural consistent retrieval entries, the hit address of the youngest address among the consistent retrieval entries is outputted. Besides, when there is no consistent retrieval entry, no hit is indicated by not outputting the hit information.
The case of a specific setting example of the CAM 400 of FIG. 19 will be further described. The retrieval entry 1900 is determined to be inconsistent since the value of b2 is different from the retrieval key 1910. The retrieval entry 1901 is determined to be inconsistent since the values of b2 and b8 are different from the retrieval key 1910. The retrieval entry 1902 is determined to be inconsistent since the value of b2 is different from the retrieval key 1910. Since the retrieval entry 1903 is the same as the retrieval key 1910, it is determined to be consistent. Since b9 of the retrieval entry 1904 is a mask bit, even if b9 of the retrieval key is 0 or 1, the bit is determined to be consistent, and the other bits are also identical to the retrieval key 1910, the retrieval entry 1904 is determined to be consistent. The retrieval entry 1905 is determined to be inconsistent since the value of b2 is different from the retrieval key 1810. Since b8 and b9 of the retrieval entry 1906 are mask bits, even if b8 and b9 of the retrieval key are 0 or 1, the bits are determined to be consistent, and since the other bits are also identical to the retrieval key 1910, the retrieval entry 1906 is determined to be consistent. The retrieval entry 1907 is determined to be inconsistent since the value of b7 is different from the retrieval key 1910. The retrieval entry 1908 is determined to be inconsistent since the value of b0 is different from the retrieval key 1910. Since all bits b0 to b9 of the retrieval entry 1909 are mask bits, even if all bits b0 to b9 of the retrieval key are 0 or 1, the retrieval entry 1909 is determined to be consistent. From the above, the retrieval entries which are determined to be consistent are the entry 1903 of address 3 of the CAM 400, the entry 1904 of address 4 of the CAM 400, the entry 1906 of address 6 of the CAM 400, and the entry 1909 of address n of the CAM 400, and there are plural retrieval entries which are consistent. Among them, the retrieval entry of the youngest address is the retrieval entry 1903 of address 3, and therefore, the hit information and the hit address 3 are outputted (1911).
Non-patent document 1: “Energy Problem of Information Communication—Power Saving of Desired Communication Infrastructure”, Ogasawara, June 2006, report of Ministry of Education, Culture, Sports, Science and Technology, National Institute of Science and Technology Policy, Science and Technology Trends Research Center, http://www.nistep.go.jp/achiev/ftx/jpn/stfc/stt063j/0606—03_fe aturearticles/0606fa 01/200606_fa01.html
Non-patent document 2: “Power Saving System of Database Retrieval For Transfer in Network Node”, Oku et al., 2005, The Institute of Electronics, Information and Communication Engineers, General Meeting B-6-153
Non-patent document 3: RFC2475, “An Architecture for Differentiated Services”, December 1998
Non-patent document 4: RFC2597, “Assured Forwarding PHB Group”, June 1999
Non-patent document 5: RFC2598, “An Expedited Forwarding PHB”, June 1999
Non-patent document 6: RFC3697, “IPv6 Flow Label Specification”, March 2004